package com.kevinkk.dp;

/**
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 * 返回 你可以获得的最大乘积。
 */

/**
 * 1. dp 数组的含义
 *      dp[i] 表示 拆分整数 i 可以获得的最大乘积
 * 2. dp 公式
 *      dp[i] = max(dp[i], max(dp[i-j] * j, (i-j) * j))
 *      dp[i] 可以拆分为 (i-j) * j，其中 (i-j) 又可以做进一步的拆分
 * 3. dp 数组的初始化
 *      显然 dp[0] 和 dp[1] 都是没有任何意义的，但是由于递推公式的需要，需要做乘法
 *      因此将二者初始化为 1
 * 4. dp 数组的遍历方式
 */

public class IntegerBreak {
    class Solution {
        public int integerBreak(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j < i / 2; j++) {
                    dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
                }
            }
            return dp[n];
        }
    }
}
